#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

/*
423. 从英文中重建数字
已解答
中等
相关标签
相关企业
给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

 

示例 1：

输入：s = "owoztneoer"
输出："012"
示例 2：

输入：s = "fviefuro"
输出："45"
 

提示：

1 <= s.length <= 105
s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
s 保证是一个符合题目要求的字符串
*/

// 法一
class Solution {
public:
    string originalDigits(string s) {
        // 字母计数
        vector<int> letterCount(26, 0);
        for(char c : s) {
            letterCount[c - 'a']++;
        }

        // 存储数字计数
        vector<int> digitCount(10, 0);

        // 通过唯一字符确定数字
        // 数字0到9的唯一字符依次是：z, w, u, x, g, s, v, o, h, i
        digitCount[0] = letterCount['z' - 'a'];  // "zero"
        digitCount[2] = letterCount['w' - 'a'];  // "two"
        digitCount[4] = letterCount['u' - 'a'];  // "four"
        digitCount[6] = letterCount['x' - 'a'];  // "six"
        digitCount[8] = letterCount['g' - 'a'];  // "eight"

        // 处理剩余的数字
        digitCount[3] = letterCount['h' - 'a'] - digitCount[8];  // "three"
        digitCount[5] = letterCount['f' - 'a'] - digitCount[4];  // "five"
        digitCount[7] = letterCount['s' - 'a'] - digitCount[6];  // "seven"
        digitCount[1] = letterCount['o' - 'a'] - digitCount[0] - digitCount[2] - digitCount[4];  // "one"
        digitCount[9] = letterCount['i' - 'a'] - digitCount[5] - digitCount[6] - digitCount[8];  // "nine"

        // 结果字符串
        string ans = "";
        for(int i = 0; i < 10; ++i) {
            ans += string(digitCount[i], '0' + i);
        }
        return ans;
    }
};

// 法二
// 基础加上哈希，更为优化
class Solution {
public:
    string originalDigits(string s) {
        // 使用 unordered_map 来统计每个字符的出现次数
        unordered_map<char, int> c;
        for (char ch: s) {
            ++c[ch];  // 对字符串中的每个字符进行计数
        }

        // cnt 数组存储每个数字（0-9）出现的次数
        vector<int> cnt(10);

        // 根据数字对应的唯一字母来确定数字的数量
        cnt[0] = c['z'];  // 'z' 唯一地出现在 "zero" 中，表示数字 0
        cnt[2] = c['w'];  // 'w' 唯一地出现在 "two" 中，表示数字 2
        cnt[4] = c['u'];  // 'u' 唯一地出现在 "four" 中，表示数字 4
        cnt[6] = c['x'];  // 'x' 唯一地出现在 "six" 中，表示数字 6
        cnt[8] = c['g'];  // 'g' 唯一地出现在 "eight" 中，表示数字 8

        // 处理剩余的数字
        cnt[3] = c['h'] - cnt[8];  // 'h' 出现在 "three" 和 "eight" 中，减去 "eight" 后得到 "three"
        cnt[5] = c['f'] - cnt[4];  // 'f' 出现在 "five" 和 "four" 中，减去 "four" 后得到 "five"
        cnt[7] = c['s'] - cnt[6];  // 's' 出现在 "seven" 和 "six" 中，减去 "six" 后得到 "seven"

        // 计算数字 1，'o' 出现在 "one", "zero", "two", "four" 中，减去其他数字的数量得到 "one"
        cnt[1] = c['o'] - cnt[0] - cnt[2] - cnt[4];

        // 计算数字 9，'i' 出现在 "nine", "five", "six", "eight" 中，减去其他数字的数量得到 "nine"
        cnt[9] = c['i'] - cnt[5] - cnt[6] - cnt[8];

        // 构建结果字符串，按数字升序排列
        string ans;
        for (int i = 0; i < 10; ++i) {
            // 将每个数字按其计数添加到结果字符串中
            for (int j = 0; j < cnt[i]; ++j) {
                ans += char(i + '0');  // 'i + '0'' 将数字 i 转换为字符
            }
        }
        return ans;  // 返回构建好的字符串，包含所有数字
    }
};